package Hot100.Medium.String_2Pointer.String;

import java.util.HashMap;

/**
 * 无重复字符的最长字串
 */
public class LC03_LenOfLongestSubString {
    public static void main(String[] args) {
        String s1 = "tmmzuxt";
        LC03_LenOfLongestSubString solution = new LC03_LenOfLongestSubString();
        System.out.println(solution.lengthOfLongestSubstring(s1));
    }

    /**
     * map里放字符的位置，便于操作，相比于第二种方法更加简单
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s){
        if(s.isEmpty()) return 0;
        int left = 0;
        int right = 0;
        int length = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        while(right < s.length()){
            char curChar = s.charAt(right);
            //如果字符存在且索引大于left，则当前窗口内有重复元素
            if(map.containsKey(curChar) && map.get(curChar) >= left){
                left = map.get(curChar) + 1;
            }
            map.put(curChar, right);
            length = Math.max(length, right - left + 1);
            right++;
        }
        return length;
    }

    /**
     * map里放字符出现的次数，为1时证明有重复字符，收缩窗口
     * 不如第一种方法方便
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s){
        if(s.isEmpty()) return 0;
        int left = 0;
        int right = 0;
        int length = 0;
        char[] arr = s.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        while(right < s.length()) {
            char curChar = arr[right];
            int count = map.getOrDefault(curChar, 0);
            //有重复字符，则从left开始一直寻找，直到找到第一次出现这个重复字符的下标
            if (count == 1) {
                while (arr[left] != curChar) {
                    map.put(arr[left], 0);
                    left++;
                }
                map.put(arr[left], 0);
                left++;
            }
            map.put(arr[right], 1);
            length = Math.max(length, right - left + 1);
            right++;
        }
        return length;
    }

}
